Théorème de Bachet-Bézout

Théorème

Soit \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}\) non nuls. Soit \(d \in \mathbb{Z}\) .
\(d=\mathrm{PGCD}(a;b)\) si, et seulement si, \(\left\lbrace \begin{array}{l} d \text{ divise } a \\ d \text{ divise } b \\ \text{il existe } (u;v) \in \mathbb{Z}^2 \text{ tel que } au+bv=d. \end{array} \right.\)  

Remarques

• Ce théorème généralise le théorème de Bézout, qui est le cas particulier où \(d=1\) .
• L'égalité \(au+bv=d=\mathrm{PGCD}(a;b)\) est appelée une identité de Bézout. Pour déterminer un couple  \((u;v) \in \mathbb{Z}^2\) qui satisfait cette égalité, on peut utiliser la méthode de remontée de l'algorithme d'Euclide.
  

Démonstration

On procède par double implication.

\([\Rightarrow]\) Supposons que \(d=\mathrm{PGCD}(a;b)\) .
D'après la propriété caractéristique du PGCD, il existe \((a';b') \in \mathbb{Z}^2\) tel que \(a=a'd\) , \(b=b'd\) et \(\mathrm{PGCD}(a';b')=1\) . Par conséquent, \(d\) divise \(a\) et \(b\) .
De plus, d'après le théorème de Bézout, il existe \((u;v) \in \mathbb{Z}^2\) tel que \(a'u+b'v=1\) .
En multipliant cette égalité par \(d>0\) , on obtient : \(\begin{align*} a'du+b'dv=d \ \ \Longleftrightarrow \ \ au+bv=d. \end{align*}\)

\([\Leftarrow]\) Supposons que \(d\) divise \(a\) et \(b\) , et qu'il existe \((u;v) \in \mathbb{Z}^2\) tel que \(au+bv=d\) .
Soit \(k \in \mathscr{D}(a;b)\) . Comme \(k\) divise \(a\) et \(b\) , \(k\) divise toute combinaison linéaire de \(a\) et \(b\) , notamment \(au+bv\) , donc \(k\) divise \(d\) .

On en déduit que \(k \leqslant d\) et ainsi, l'ensemble \(\mathscr{D}(a;b)\) est majoré par \(d\) .
Or \(d\) divise \(a\) et \(b\) , donc \(d \in \mathscr{D}(a;b)\) , ce qui prouve que \(d\) est le plus grand élément de \(\mathscr{D}(a;b)\) , c'est-à-dire \(d=\mathrm{PGCD}(a;b)\) .